home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 14 / CU Amiga Magazine's Super CD-ROM 14 (1997)(EMAP Images)(GB)(Track 1 of 3)[!][issue 1997-09].iso / CUCD / Programming / Mesa-2.2 / src / tritemp.h < prev    next >
Encoding:
Text File  |  1997-03-14  |  29.3 KB  |  857 lines
  1. /* $Id: tritemp.h,v 1.12 1997/03/14 00:25:02 brianp Exp $ */
  2.  
  3. /*
  4.  * Mesa 3-D graphics library
  5.  * Version:  2.1
  6.  * Copyright (C) 1995-1996  Brian Paul
  7.  *
  8.  * This library is free software; you can redistribute it and/or
  9.  * modify it under the terms of the GNU Library General Public
  10.  * License as published by the Free Software Foundation; either
  11.  * version 2 of the License, or (at your option) any later version.
  12.  *
  13.  * This library is distributed in the hope that it will be useful,
  14.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16.  * Library General Public License for more details.
  17.  *
  18.  * You should have received a copy of the GNU Library General Public
  19.  * License along with this library; if not, write to the Free
  20.  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21.  */
  22.  
  23.  
  24. /*
  25.  * $Log: tritemp.h,v $
  26.  * Revision 1.12  1997/03/14 00:25:02  brianp
  27.  * fixed unitialized memory read, contributed by Tom Schmidt
  28.  *
  29.  * Revision 1.11  1997/02/09 18:51:10  brianp
  30.  * fixed typo in texture R interpolation code
  31.  *
  32.  * Revision 1.10  1996/12/20 23:12:23  brianp
  33.  * another attempt at preventing color interpolation over/underflow
  34.  *
  35.  * Revision 1.9  1996/12/18 20:38:25  brianp
  36.  * commented out unused zp declaration
  37.  *
  38.  * Revision 1.8  1996/12/12 22:37:49  brianp
  39.  * projective textures didn't work right
  40.  *
  41.  * Revision 1.7  1996/11/02 06:17:37  brianp
  42.  * fixed some float/int roundoff and over/underflow errors (hopefully)
  43.  *
  44.  * Revision 1.6  1996/10/01 04:13:09  brianp
  45.  * fixed Z interpolation for >16-bit depth buffer
  46.  * added color underflow error check
  47.  *
  48.  * Revision 1.5  1996/09/27 01:32:59  brianp
  49.  * removed unused variables
  50.  *
  51.  * Revision 1.4  1996/09/18 01:03:43  brianp
  52.  * tightened threshold for culling by area
  53.  *
  54.  * Revision 1.3  1996/09/15 14:19:16  brianp
  55.  * now use GLframebuffer and GLvisual
  56.  *
  57.  * Revision 1.2  1996/09/14 06:41:38  brianp
  58.  * perspective correct texture code wasn't sub-pixel accurate (Doug Rabson)
  59.  *
  60.  * Revision 1.1  1996/09/13 01:38:16  brianp
  61.  * Initial revision
  62.  *
  63.  */
  64.  
  65.  
  66. /*
  67.  * Triangle Rasterizer Template
  68.  *
  69.  * This file is #include'd to generate custom triangle rasterizers.
  70.  *
  71.  * The following macros may be defined to indicate what auxillary information
  72.  * must be interplated across the triangle:
  73.  *    INTERP_Z      - if defined, interpolate Z values
  74.  *    INTERP_RGB    - if defined, interpolate RGB values
  75.  *    INTERP_ALPHA  - if defined, interpolate Alpha values
  76.  *    INTERP_INDEX  - if defined, interpolate color index values
  77.  *    INTERP_ST     - if defined, interpolate integer ST texcoords
  78.  *                         (fast, simple 2-D texture mapping)
  79.  *    INTERP_STW    - if defined, interpolate float ST texcoords and W
  80.  *                         (2-D texture maps with perspective correction)
  81.  *    INTERP_UV     - if defined, interpolate float UV texcoords too
  82.  *                         (for 3-D, 4-D? texture maps)
  83.  *
  84.  * When one can directly address pixels in the color buffer the following
  85.  * macros can be defined and used to compute pixel addresses during
  86.  * rasterization (see pRow):
  87.  *    PIXEL_TYPE          - the datatype of a pixel (GLubyte, GLushort, GLuint)
  88.  *    BYTES_PER_ROW       - number of bytes per row in the color buffer
  89.  *    PIXEL_ADDRESS(X,Y)  - returns the address of pixel at (X,Y) where
  90.  *                          Y==0 at bottom of screen and increases upward.
  91.  *
  92.  * Optionally, one may provide one-time setup code per triangle:
  93.  *    SETUP_CODE    - code which is to be executed once per triangle
  94.  * 
  95.  * The following macro MUST be defined:
  96.  *    INNER_LOOP(LEFT,RIGHT,Y) - code to write a span of pixels.
  97.  *        Something like:
  98.  *
  99.  *                    for (x=LEFT; x<RIGHT;x++) {
  100.  *                       put_pixel(x,Y);
  101.  *                       // increment fixed point interpolants
  102.  *                    }
  103.  *
  104.  * This code was designed for the origin to be in the lower-left corner.
  105.  *
  106.  * Inspired by triangle rasterizer code written by Allen Akin.  Thanks Allen!
  107.  */
  108.  
  109.  
  110. /*void triangle( GLcontext *ctx, GLuint v0, GLuint v1, GLuint v2, GLuint pv )*/
  111. {
  112.    typedef struct {
  113.         GLint v0, v1;     /* Y(v0) < Y(v1) */
  114.     GLfloat dx;    /* X(v1) - X(v0) */
  115.     GLfloat dy;    /* Y(v1) - Y(v0) */
  116.     GLfixed fdxdy;    /* dx/dy in fixed-point */
  117.     GLfixed fsx;    /* first sample point x coord */
  118.     GLfixed fsy;
  119.     GLfloat adjy;    /* adjust from v[0]->fy to fsy, scaled */
  120.     GLint lines;    /* number of lines to be sampled on this edge */
  121.     GLfixed fx0;    /* fixed pt X of lower endpoint */
  122.    } EdgeT;
  123.  
  124.    struct vertex_buffer *VB = ctx->VB;
  125.    EdgeT eMaj, eTop, eBot;
  126.    GLfloat oneOverArea;
  127.    int vMin, vMid, vMax;       /* vertex indexes:  Y(vMin)<=Y(vMid)<=Y(vMax) */
  128.  
  129.    /* find the order of the 3 vertices along the Y axis */
  130.    {
  131.       GLfloat y0 = VB->Win[v0][1];
  132.       GLfloat y1 = VB->Win[v1][1];
  133.       GLfloat y2 = VB->Win[v2][1];
  134.  
  135.       if (y0<=y1) {
  136.      if (y1<=y2) {
  137.         vMin = v0;   vMid = v1;   vMax = v2;   /* y0<=y1<=y2 */
  138.      }
  139.      else if (y2<=y0) {
  140.         vMin = v2;   vMid = v0;   vMax = v1;   /* y2<=y0<=y1 */
  141.      }
  142.      else {
  143.         vMin = v0;   vMid = v2;   vMax = v1;   /* y0<=y2<=y1 */
  144.      }
  145.       }
  146.       else {
  147.      if (y0<=y2) {
  148.         vMin = v1;   vMid = v0;   vMax = v2;   /* y1<=y0<=y2 */
  149.      }
  150.      else if (y2<=y1) {
  151.         vMin = v2;   vMid = v1;   vMax = v0;   /* y2<=y1<=y0 */
  152.      }
  153.      else {
  154.         vMin = v1;   vMid = v2;   vMax = v0;   /* y1<=y2<=y0 */
  155.      }
  156.       }
  157.    }
  158.  
  159.    /* vertex/edge relationship */
  160.    eMaj.v0 = vMin;   eMaj.v1 = vMax;   /*TODO: .v1's not needed */
  161.    eTop.v0 = vMid;   eTop.v1 = vMax;
  162.    eBot.v0 = vMin;   eBot.v1 = vMid;
  163.  
  164.    /* compute deltas for each edge:  vertex[v1] - vertex[v0] */
  165.    eMaj.dx = VB->Win[vMax][0] - VB->Win[vMin][0];
  166.    eMaj.dy = VB->Win[vMax][1] - VB->Win[vMin][1];
  167.    eTop.dx = VB->Win[vMax][0] - VB->Win[vMid][0];
  168.    eTop.dy = VB->Win[vMax][1] - VB->Win[vMid][1];
  169.    eBot.dx = VB->Win[vMid][0] - VB->Win[vMin][0];
  170.    eBot.dy = VB->Win[vMid][1] - VB->Win[vMin][1];
  171.  
  172.    /* compute oneOverArea */
  173.    {
  174.       GLfloat area = eMaj.dx * eBot.dy - eBot.dx * eMaj.dy;
  175.       if (area>-0.05f && area<0.05f) {
  176.          return;  /* very small; CULLED */
  177.       }
  178.       oneOverArea = 1.0F / area;
  179.    }
  180.  
  181.    /* Edge setup.  For a triangle strip these could be reused... */
  182.    {
  183.       /* fixed point Y coordinates */
  184.       GLfixed vMin_fx = FloatToFixed(VB->Win[vMin][0] + 0.5F);
  185.       GLfixed vMin_fy = FloatToFixed(VB->Win[vMin][1] - 0.5F);
  186.       GLfixed vMid_fx = FloatToFixed(VB->Win[vMid][0] + 0.5F);
  187.       GLfixed vMid_fy = FloatToFixed(VB->Win[vMid][1] - 0.5F);
  188.       GLfixed vMax_fy = FloatToFixed(VB->Win[vMax][1] - 0.5F);
  189.  
  190.       eMaj.fsy = FixedCeil(vMin_fy);
  191.       eMaj.lines = FixedToInt(vMax_fy + FIXED_ONE - FIXED_EPSILON - eMaj.fsy);
  192.       if (eMaj.lines > 0) {
  193.          GLfloat dxdy = eMaj.dx / eMaj.dy;
  194.          eMaj.fdxdy = SignedFloatToFixed(dxdy);
  195.          eMaj.adjy = (GLfloat) (eMaj.fsy - vMin_fy);  /* SCALED! */
  196.          eMaj.fx0 = vMin_fx;
  197.          eMaj.fsx = eMaj.fx0 + (GLfixed) (eMaj.adjy * dxdy);
  198.       }
  199.       else {
  200.          return;  /*CULLED*/
  201.       }
  202.  
  203.       eTop.fsy = FixedCeil(vMid_fy);
  204.       eTop.lines = FixedToInt(vMax_fy + FIXED_ONE - FIXED_EPSILON - eTop.fsy);
  205.       if (eTop.lines > 0) {
  206.          GLfloat dxdy = eTop.dx / eTop.dy;
  207.          eTop.fdxdy = SignedFloatToFixed(dxdy);
  208.          eTop.adjy = (GLfloat) (eTop.fsy - vMid_fy); /* SCALED! */
  209.          eTop.fx0 = vMid_fx;
  210.          eTop.fsx = eTop.fx0 + (GLfixed) (eTop.adjy * dxdy);
  211.       }
  212.  
  213.       eBot.fsy = FixedCeil(vMin_fy);
  214.       eBot.lines = FixedToInt(vMid_fy + FIXED_ONE - FIXED_EPSILON - eBot.fsy);
  215.       if (eBot.lines > 0) {
  216.          GLfloat dxdy = eBot.dx / eBot.dy;
  217.          eBot.fdxdy = SignedFloatToFixed(dxdy);
  218.          eBot.adjy = (GLfloat) (eBot.fsy - vMin_fy);  /* SCALED! */
  219.          eBot.fx0 = vMin_fx;
  220.          eBot.fsx = eBot.fx0 + (GLfixed) (eBot.adjy * dxdy);
  221.       }
  222.    }
  223.  
  224.    /*
  225.     * Conceptually, we view a triangle as two subtriangles
  226.     * separated by a perfectly horizontal line.  The edge that is
  227.     * intersected by this line is one with maximal absolute dy; we
  228.     * call it a ``major'' edge.  The other two edges are the
  229.     * ``top'' edge (for the upper subtriangle) and the ``bottom''
  230.     * edge (for the lower subtriangle).  If either of these two
  231.     * edges is horizontal or very close to horizontal, the
  232.     * corresponding subtriangle might cover zero sample points;
  233.     * we take care to handle such cases, for performance as well
  234.     * as correctness.
  235.     *
  236.     * By stepping rasterization parameters along the major edge,
  237.     * we can avoid recomputing them at the discontinuity where
  238.     * the top and bottom edges meet.  However, this forces us to
  239.     * be able to scan both left-to-right and right-to-left. 
  240.     * Also, we must determine whether the major edge is at the
  241.     * left or right side of the triangle.  We do this by
  242.     * computing the magnitude of the cross-product of the major
  243.     * and top edges.  Since this magnitude depends on the sine of
  244.     * the angle between the two edges, its sign tells us whether
  245.     * we turn to the left or to the right when travelling along
  246.     * the major edge to the top edge, and from this we infer
  247.     * whether the major edge is on the left or the right.
  248.     *
  249.     * Serendipitously, this cross-product magnitude is also a
  250.     * value we need to compute the iteration parameter
  251.     * derivatives for the triangle, and it can be used to perform
  252.     * backface culling because its sign tells us whether the
  253.     * triangle is clockwise or counterclockwise.  In this code we
  254.     * refer to it as ``area'' because it's also proportional to
  255.     * the pixel area of the triangle.
  256.     */
  257.  
  258.    {
  259.       GLint ltor;        /* true if scanning left-to-right */
  260. #if INTERP_Z
  261.       GLfloat dzdx, dzdy;      GLfixed fdzdx;
  262. #endif
  263. #if INTERP_RGB
  264.       GLfloat drdx, drdy;      GLfixed fdrdx;
  265.       GLfloat dgdx, dgdy;      GLfixed fdgdx;
  266.       GLfloat dbdx, dbdy;      GLfixed fdbdx;
  267. #endif
  268. #if INTERP_ALPHA
  269.       GLfloat dadx, dady;      GLfixed fdadx;
  270. #endif
  271. #if INTERP_INDEX
  272.       GLfloat didx, didy;      GLfixed fdidx;
  273. #endif
  274. #if INTERP_ST
  275.       GLfloat dsdx, dsdy;      GLfixed fdsdx;
  276.       GLfloat dtdx, dtdy;      GLfixed fdtdx;
  277. #endif
  278. #if INTERP_STW
  279.       GLfloat dsdx, dsdy;
  280.       GLfloat dtdx, dtdy;
  281.       GLfloat dwdx, dwdy;
  282. #endif
  283. #if INTERP_UV
  284.       GLfloat dudx, dudy;
  285.       GLfloat dvdx, dvdy;
  286. #endif
  287.  
  288.       /*
  289.        * Execute user-supplied setup code
  290.        */
  291. #ifdef SETUP_CODE
  292.       SETUP_CODE
  293. #endif
  294.  
  295.       ltor = (oneOverArea < 0.0F);
  296.  
  297.       /* compute d?/dx and d?/dy derivatives */
  298. #if INTERP_Z
  299.       {
  300.          GLfloat eMaj_dz, eBot_dz;
  301.          eMaj_dz = VB->Win[vMax][2] - VB->Win[vMin][2];
  302.          eBot_dz = VB->Win[vMid][2] - VB->Win[vMin][2];
  303.          dzdx = oneOverArea * (eMaj_dz * eBot.dy - eMaj.dy * eBot_dz);
  304.          if (dzdx>DEPTH_SCALE || dzdx<-DEPTH_SCALE) {
  305.             /* probably a sliver triangle */
  306.             dzdx = 0.0;
  307.             dzdy = 0.0;
  308.          }
  309.          else {
  310.             dzdy = oneOverArea * (eMaj.dx * eBot_dz - eMaj_dz * eBot.dx);
  311.          }
  312. #if DEPTH_BITS==16
  313.          fdzdx = SignedFloatToFixed(dzdx);
  314. #else
  315.          fdzdx = (GLint) dzdx;
  316. #endif
  317.       }
  318. #endif
  319. #if INTERP_RGB
  320.       {
  321.          GLfloat eMaj_dr, eBot_dr;
  322.          eMaj_dr = FixedToFloat( VB->Color[vMax][0] - VB->Color[vMin][0] );
  323.          eBot_dr = FixedToFloat( VB->Color[vMid][0] - VB->Color[vMin][0] );
  324.          drdx = oneOverArea * (eMaj_dr * eBot.dy - eMaj.dy * eBot_dr);
  325.          fdrdx = SignedFloatToFixed(drdx);
  326.          drdy = oneOverArea * (eMaj.dx * eBot_dr - eMaj_dr * eBot.dx);
  327.       }
  328.       {
  329.          GLfloat eMaj_dg, eBot_dg;
  330.          eMaj_dg = FixedToFloat( VB->Color[vMax][1] - VB->Color[vMin][1] );
  331.      eBot_dg = FixedToFloat( VB->Color[vMid][1] - VB->Color[vMin][1] );
  332.          dgdx = oneOverArea * (eMaj_dg * eBot.dy - eMaj.dy * eBot_dg);
  333.          fdgdx = SignedFloatToFixed(dgdx);
  334.          dgdy = oneOverArea * (eMaj.dx * eBot_dg - eMaj_dg * eBot.dx);
  335.       }
  336.       {
  337.          GLfloat eMaj_db, eBot_db;
  338.          eMaj_db = FixedToFloat( VB->Color[vMax][2] - VB->Color[vMin][2] );
  339.          eBot_db = FixedToFloat( VB->Color[vMid][2] - VB->Color[vMin][2] );
  340.          dbdx = oneOverArea * (eMaj_db * eBot.dy - eMaj.dy * eBot_db);
  341.          fdbdx = SignedFloatToFixed(dbdx);
  342.      dbdy = oneOverArea * (eMaj.dx * eBot_db - eMaj_db * eBot.dx);
  343.       }
  344. #endif
  345. #if INTERP_ALPHA
  346.       {
  347.          GLfloat eMaj_da, eBot_da;
  348.          eMaj_da = FixedToFloat( VB->Color[vMax][3] - VB->Color[vMin][3] );
  349.          eBot_da = FixedToFloat( VB->Color[vMid][3] - VB->Color[vMin][3] );
  350.          dadx = oneOverArea * (eMaj_da * eBot.dy - eMaj.dy * eBot_da);
  351.          fdadx = SignedFloatToFixed(dadx);
  352.          dady = oneOverArea * (eMaj.dx * eBot_da - eMaj_da * eBot.dx);
  353.       }
  354. #endif
  355. #if INTERP_INDEX
  356.       {
  357.          GLfloat eMaj_di, eBot_di;
  358.          eMaj_di = (GLint) VB->Index[vMax] - (GLint) VB->Index[vMin];
  359.          eBot_di = (GLint) VB->Index[vMid] - (GLint) VB->Index[vMin];
  360.          didx = oneOverArea * (eMaj_di * eBot.dy - eMaj.dy * eBot_di);
  361.          fdidx = SignedFloatToFixed(didx);
  362.          didy = oneOverArea * (eMaj.dx * eBot_di - eMaj_di * eBot.dx);
  363.       }
  364. #endif
  365. #if INTERP_ST
  366.       {
  367.          GLfloat eMaj_ds, eBot_ds;
  368.          eMaj_ds = (VB->TexCoord[vMax][0] - VB->TexCoord[vMin][0]) * S_SCALE;
  369.          eBot_ds = (VB->TexCoord[vMid][0] - VB->TexCoord[vMin][0]) * T_SCALE;
  370.          dsdx = oneOverArea * (eMaj_ds * eBot.dy - eMaj.dy * eBot_ds);
  371.          fdsdx = SignedFloatToFixed(dsdx);
  372.          dsdy = oneOverArea * (eMaj.dx * eBot_ds - eMaj_ds * eBot.dx);
  373.       }
  374.       {
  375.          GLfloat eMaj_dt, eBot_dt;
  376.          eMaj_dt = (VB->TexCoord[vMax][1] - VB->TexCoord[vMin][1]) * S_SCALE;
  377.          eBot_dt = (VB->TexCoord[vMid][1] - VB->TexCoord[vMin][1]) * T_SCALE;
  378.          dtdx = oneOverArea * (eMaj_dt * eBot.dy - eMaj.dy * eBot_dt);
  379.          fdtdx = SignedFloatToFixed(dtdx);
  380.          dtdy = oneOverArea * (eMaj.dx * eBot_dt - eMaj_dt * eBot.dx);
  381.       }
  382. #endif
  383. #if INTERP_STW
  384.       {
  385.          GLfloat wMax = 1.0F / VB->Clip[vMax][3];
  386.          GLfloat wMin = 1.0F / VB->Clip[vMin][3];
  387.          GLfloat wMid = 1.0F / VB->Clip[vMid][3];
  388.          GLfloat eMaj_dw, eBot_dw;
  389.          GLfloat eMaj_ds, eBot_ds;
  390.          GLfloat eMaj_dt, eBot_dt;
  391. #if INTERP_UV
  392.          GLfloat eMaj_du, eBot_du;
  393.          GLfloat eMaj_dv, eBot_dv;
  394. #endif
  395.          eMaj_dw = wMax - wMin;
  396.          eBot_dw = wMid - wMin;
  397.          dwdx = oneOverArea * (eMaj_dw * eBot.dy - eMaj.dy * eBot_dw);
  398.          dwdy = oneOverArea * (eMaj.dx * eBot_dw - eMaj_dw * eBot.dx);
  399.  
  400.          eMaj_ds = VB->TexCoord[vMax][0]*wMax - VB->TexCoord[vMin][0]*wMin;
  401.          eBot_ds = VB->TexCoord[vMid][0]*wMid - VB->TexCoord[vMin][0]*wMin;
  402.          dsdx = oneOverArea * (eMaj_ds * eBot.dy - eMaj.dy * eBot_ds);
  403.          dsdy = oneOverArea * (eMaj.dx * eBot_ds - eMaj_ds * eBot.dx);
  404.  
  405.          eMaj_dt = VB->TexCoord[vMax][1]*wMax - VB->TexCoord[vMin][1]*wMin;
  406.          eBot_dt = VB->TexCoord[vMid][1]*wMid - VB->TexCoord[vMin][1]*wMin;
  407.          dtdx = oneOverArea * (eMaj_dt * eBot.dy - eMaj.dy * eBot_dt);
  408.          dtdy = oneOverArea * (eMaj.dx * eBot_dt - eMaj_dt * eBot.dx);
  409. #if INTERP_UV
  410.          eMaj_du = VB->TexCoord[vMax][2]*wMax - VB->TexCoord[vMin][2]*wMin;
  411.          eBot_du = VB->TexCoord[vMid][2]*wMid - VB->TexCoord[vMin][2]*wMin;
  412.          dudx = oneOverArea * (eMaj_du * eBot.dy - eMaj.dy * eBot_du);
  413.          dudy = oneOverArea * (eMaj.dx * eBot_du - eMaj_du * eBot.dx);
  414.  
  415.          /* Note: don't divide V component by W */
  416.          eMaj_dv = VB->TexCoord[vMax][3] - VB->TexCoord[vMin][3];
  417.          eBot_dv = VB->TexCoord[vMid][3] - VB->TexCoord[vMin][3];
  418.          dvdx = oneOverArea * (eMaj_dv * eBot.dy - eMaj.dy * eBot_dv);
  419.          dvdy = oneOverArea * (eMaj.dx * eBot_dv - eMaj_dv * eBot.dx);
  420. #endif
  421.       }
  422. #endif
  423.  
  424.       /*
  425.        * We always sample at pixel centers.  However, we avoid
  426.        * explicit half-pixel offsets in this code by incorporating
  427.        * the proper offset in each of x and y during the
  428.        * transformation to window coordinates.
  429.        *
  430.        * We also apply the usual rasterization rules to prevent
  431.        * cracks and overlaps.  A pixel is considered inside a
  432.        * subtriangle if it meets all of four conditions: it is on or
  433.        * to the right of the left edge, strictly to the left of the
  434.        * right edge, on or below the top edge, and strictly above
  435.        * the bottom edge.  (Some edges may be degenerate.)
  436.        *
  437.        * The following discussion assumes left-to-right scanning
  438.        * (that is, the major edge is on the left); the right-to-left
  439.        * case is a straightforward variation.
  440.        *
  441.        * We start by finding the half-integral y coordinate that is
  442.        * at or below the top of the triangle.  This gives us the
  443.        * first scan line that could possibly contain pixels that are
  444.        * inside the triangle.
  445.        *
  446.        * Next we creep down the major edge until we reach that y,
  447.        * and compute the corresponding x coordinate on the edge. 
  448.        * Then we find the half-integral x that lies on or just
  449.        * inside the edge.  This is the first pixel that might lie in
  450.        * the interior of the triangle.  (We won't know for sure
  451.        * until we check the other edges.)
  452.        *
  453.        * As we rasterize the triangle, we'll step down the major
  454.        * edge.  For each step in y, we'll move an integer number
  455.        * of steps in x.  There are two possible x step sizes, which
  456.        * we'll call the ``inner'' step (guaranteed to land on the
  457.        * edge or inside it) and the ``outer'' step (guaranteed to
  458.        * land on the edge or outside it).  The inner and outer steps
  459.        * differ by one.  During rasterization we maintain an error
  460.        * term that indicates our distance from the true edge, and
  461.        * select either the inner step or the outer step, whichever
  462.        * gets us to the first pixel that falls inside the triangle.
  463.        *
  464.        * All parameters (z, red, etc.) as well as the buffer
  465.        * addresses for color and z have inner and outer step values,
  466.        * so that we can increment them appropriately.  This method
  467.        * eliminates the need to adjust parameters by creeping a
  468.        * sub-pixel amount into the triangle at each scanline.
  469.        */
  470.  
  471.       {
  472.          int subTriangle;
  473.          GLfixed fx, fxLeftEdge, fxRightEdge, fdxLeftEdge, fdxRightEdge;
  474.          GLfixed fdxOuter;
  475.          int idxOuter;
  476.          float dxOuter;
  477.          GLfixed fError, fdError;
  478.          float adjx, adjy;
  479.          GLfixed fy;
  480.          int iy;
  481. #ifdef PIXEL_ADDRESS
  482.          PIXEL_TYPE *pRow;
  483.          int dPRowOuter, dPRowInner;  /* offset in bytes */
  484. #endif
  485. #if INTERP_Z
  486.          GLdepth *zRow;
  487.          int dZRowOuter, dZRowInner;  /* offset in bytes */
  488.          GLfixed fz, fdzOuter, fdzInner;
  489. #endif
  490. #if INTERP_RGB
  491.          GLfixed fr, fdrOuter, fdrInner;
  492.          GLfixed fg, fdgOuter, fdgInner;
  493.          GLfixed fb, fdbOuter, fdbInner;
  494. #endif
  495. #if INTERP_ALPHA
  496.          GLfixed fa, fdaOuter, fdaInner;
  497. #endif
  498. #if INTERP_INDEX
  499.          GLfixed fi, fdiOuter, fdiInner;
  500. #endif
  501. #if INTERP_ST
  502.          GLfixed fs, fdsOuter, fdsInner;
  503.          GLfixed ft, fdtOuter, fdtInner;
  504. #endif
  505. #if INTERP_STW
  506.          GLfloat sLeft, dsOuter, dsInner;
  507.          GLfloat tLeft, dtOuter, dtInner;
  508.          GLfloat wLeft, dwOuter, dwInner;
  509. #endif
  510. #if INTERP_UV
  511.          GLfloat uLeft, duOuter, duInner;
  512.          GLfloat vLeft, dvOuter, dvInner;
  513. #endif
  514.  
  515.          for (subTriangle=0; subTriangle<=1; subTriangle++) {
  516.             EdgeT *eLeft, *eRight;
  517.             int setupLeft, setupRight;
  518.             int lines;
  519.  
  520.             if (subTriangle==0) {
  521.                /* bottom half */
  522.                if (ltor) {
  523.                   eLeft = &eMaj;
  524.                   eRight = &eBot;
  525.                   lines = eRight->lines;
  526.                   setupLeft = 1;
  527.                   setupRight = 1;
  528.                }
  529.                else {
  530.                   eLeft = &eBot;
  531.                   eRight = &eMaj;
  532.                   lines = eLeft->lines;
  533.                   setupLeft = 1;
  534.                   setupRight = 1;
  535.                }
  536.             }
  537.             else {
  538.                /* top half */
  539.                if (ltor) {
  540.                   eLeft = &eMaj;
  541.                   eRight = &eTop;
  542.                   lines = eRight->lines;
  543.                   setupLeft = 0;
  544.                   setupRight = 1;
  545.                }
  546.                else {
  547.                   eLeft = &eTop;
  548.                   eRight = &eMaj;
  549.                   lines = eLeft->lines;
  550.                   setupLeft = 1;
  551.                   setupRight = 0;
  552.                }
  553.                if (lines==0) return;
  554.             }
  555.  
  556.             if (setupLeft && eLeft->lines>0) {
  557.                GLint vLower;
  558.                GLfixed fsx = eLeft->fsx;
  559.                fx = FixedCeil(fsx);
  560.                fError = fx - fsx - FIXED_ONE;
  561.                fxLeftEdge = fsx - FIXED_EPSILON;
  562.                fdxLeftEdge = eLeft->fdxdy;
  563.                fdxOuter = FixedFloor(fdxLeftEdge - FIXED_EPSILON);
  564.                fdError = fdxOuter - fdxLeftEdge + FIXED_ONE;
  565.                idxOuter = FixedToInt(fdxOuter);
  566.                dxOuter = (float) idxOuter;
  567.  
  568.                fy = eLeft->fsy;
  569.                iy = FixedToInt(fy);
  570.  
  571.                adjx = (float)(fx - eLeft->fx0);  /* SCALED! */
  572.                adjy = eLeft->adjy;         /* SCALED! */
  573.  
  574.                vLower = eLeft->v0;
  575.  
  576. #ifdef PIXEL_ADDRESS
  577.                {
  578.                   pRow = PIXEL_ADDRESS( FixedToInt(fxLeftEdge), iy );
  579.                   dPRowOuter = -BYTES_PER_ROW + idxOuter * sizeof(PIXEL_TYPE);
  580.                   /* negative because Y=0 at bottom and increases upward */
  581.                }
  582. #endif
  583.                /*
  584.                 * Now we need the set of parameter (z, color, etc.) values at
  585.                 * the point (fx, fy).  This gives us properly-sampled parameter
  586.                 * values that we can step from pixel to pixel.  Furthermore,
  587.                 * although we might have intermediate results that overflow
  588.                 * the normal parameter range when we step temporarily outside
  589.                 * the triangle, we shouldn't overflow or underflow for any
  590.                 * pixel that's actually inside the triangle.
  591.                 */
  592.  
  593. #if INTERP_Z
  594.                {
  595.                   GLfloat z0;
  596.                   z0 = VB->Win[vLower][2] + ctx->PolygonZoffset;
  597. #if DEPTH_BITS==16
  598.                   /* interpolate fixed-pt values */
  599.                   fz = (GLfixed)(z0 * FIXED_SCALE + dzdx * adjx + dzdy * adjy) + FIXED_HALF;
  600.                   fdzOuter = SignedFloatToFixed(dzdy + dxOuter * dzdx);
  601. #else
  602.                   /* interpolate depth values exactly */
  603.                   fz = (GLint) (z0 + dzdx*FixedToFloat(adjx) + dzdy*FixedToFloat(adjy));
  604.                   fdzOuter = (GLint) (dzdy + dxOuter * dzdx);
  605. #endif
  606.                   zRow = Z_ADDRESS( ctx, FixedToInt(fxLeftEdge), iy );
  607.                   dZRowOuter = (ctx->Buffer->Width + idxOuter) * sizeof(GLdepth);
  608.                }
  609. #endif
  610. #if INTERP_RGB
  611.                fr = (GLfixed)(VB->Color[vLower][0] + drdx * adjx + drdy * adjy)
  612.                     + FIXED_HALF;
  613.                fdrOuter = SignedFloatToFixed(drdy + dxOuter * drdx);
  614.  
  615.                fg = (GLfixed)(VB->Color[vLower][1] + dgdx * adjx + dgdy * adjy)
  616.                     + FIXED_HALF;
  617.                fdgOuter = SignedFloatToFixed(dgdy + dxOuter * dgdx);
  618.  
  619.                fb = (GLfixed)(VB->Color[vLower][2] + dbdx * adjx + dbdy * adjy)
  620.                     + FIXED_HALF;
  621.                fdbOuter = SignedFloatToFixed(dbdy + dxOuter * dbdx);
  622. #endif
  623. #if INTERP_ALPHA
  624.                fa = (GLfixed)(VB->Color[vLower][3] + dadx * adjx + dady * adjy)
  625.                     + FIXED_HALF;
  626.                fdaOuter = SignedFloatToFixed(dady + dxOuter * dadx);
  627. #endif
  628. #if INTERP_INDEX
  629.                fi = (GLfixed)(VB->Index[vLower] * FIXED_SCALE + didx * adjx
  630.                               + didy * adjy) + FIXED_HALF;
  631.                fdiOuter = SignedFloatToFixed(didy + dxOuter * didx);
  632. #endif
  633. #if INTERP_ST
  634.                {
  635.                   GLfloat s0, t0;
  636.                   s0 = VB->TexCoord[vLower][0] * S_SCALE;
  637.                   fs = (GLfixed)(s0 * FIXED_SCALE + dsdx * adjx + dsdy * adjy) + FIXED_HALF;
  638.                   fdsOuter = SignedFloatToFixed(dsdy + dxOuter * dsdx);
  639.                   t0 = VB->TexCoord[vLower][1] * T_SCALE;
  640.                   ft = (GLfixed)(t0 * FIXED_SCALE + dtdx * adjx + dtdy * adjy) + FIXED_HALF;
  641.                   fdtOuter = SignedFloatToFixed(dtdy + dxOuter * dtdx);
  642.                }
  643. #endif
  644. #if INTERP_STW
  645.                {
  646.                   GLfloat w0 = 1.0F / VB->Clip[vLower][3];
  647.                   GLfloat s0, t0, u0, v0;
  648.                   wLeft = w0 + (dwdx * adjx + dwdy * adjy) * (1.0F/FIXED_SCALE);
  649.           dwOuter = dwdy + dxOuter * dwdx;
  650.                   s0 = VB->TexCoord[vLower][0] * w0;
  651.                   sLeft = s0 + (dsdx * adjx + dsdy * adjy) * (1.0F/FIXED_SCALE);
  652.                   dsOuter = dsdy + dxOuter * dsdx;
  653.                   t0 = VB->TexCoord[vLower][1] * w0;
  654.                   tLeft = t0 + (dtdx * adjx + dtdy * adjy) * (1.0F/FIXED_SCALE);
  655.                   dtOuter = dtdy + dxOuter * dtdx;
  656. #if INTERP_UV
  657.                   u0 = VB->TexCoord[vLower][2] * w0;
  658.                   uLeft = u0 + (dudx * adjx + dudy * adjy) * (1.0F/FIXED_SCALE);
  659.                   duOuter = dudy + dxOuter * dudx;
  660.                   /* Note: don't divide V component by W */
  661.                   v0 = VB->TexCoord[vLower][3];
  662.                   vLeft = v0 + (dvdx * adjx + dvdy * adjy) * (1.0F/FIXED_SCALE);
  663.                   dvOuter = dvdy + dxOuter * dvdx;
  664. #endif
  665.                }
  666. #endif
  667.  
  668.             } /*if setupLeft*/
  669.  
  670.  
  671.             if (setupRight && eRight->lines>0) {
  672.                fxRightEdge = eRight->fsx - FIXED_EPSILON;
  673.                fdxRightEdge = eRight->fdxdy;
  674.             }
  675.  
  676.             if (lines==0) {
  677.                continue;
  678.             }
  679.  
  680.  
  681.             /* Rasterize setup */
  682. #ifdef PIXEL_ADDRESS
  683.             dPRowInner = dPRowOuter + sizeof(PIXEL_TYPE);
  684. #endif
  685. #if INTERP_Z
  686.             dZRowInner = dZRowOuter + sizeof(GLdepth);
  687.             fdzInner = fdzOuter + fdzdx;
  688. #endif
  689. #if INTERP_RGB
  690.             fdrInner = fdrOuter + fdrdx;
  691.             fdgInner = fdgOuter + fdgdx;
  692.             fdbInner = fdbOuter + fdbdx;
  693. #endif
  694. #if INTERP_ALPHA
  695.             fdaInner = fdaOuter + fdadx;
  696. #endif
  697. #if INTERP_INDEX
  698.             fdiInner = fdiOuter + fdidx;
  699. #endif
  700. #if INTERP_ST
  701.             fdsInner = fdsOuter + fdsdx;
  702.             fdtInner = fdtOuter + fdtdx;
  703. #endif
  704. #if INTERP_STW
  705.         dwInner = dwOuter + dwdx;
  706.         dsInner = dsOuter + dsdx;
  707.         dtInner = dtOuter + dtdx;
  708. #if INTERP_UV
  709.         duInner = duOuter + dudx;
  710.         dvInner = dvOuter + dvdx;
  711. #endif
  712. #endif
  713.  
  714.             while (lines>0) {
  715.                /* initialize the span interpolants to the leftmost value */
  716.                /* ff = fixed-pt fragment */
  717. #if INTERP_Z
  718.                GLfixed ffz = fz;
  719.                /*GLdepth *zp = zRow;*/
  720. #endif
  721. #if INTERP_RGB
  722.                GLfixed ffr = fr,  ffg = fg,  ffb = fb;
  723. #endif
  724. #if INTERP_ALPHA
  725.                GLfixed ffa = fa;
  726. #endif
  727. #if INTERP_INDEX
  728.                GLfixed ffi = fi;
  729. #endif
  730. #if INTERP_ST
  731.                GLfixed ffs = fs,  fft = ft;
  732. #endif
  733. #if INTERP_STW
  734.                GLfloat ss = sLeft,  tt = tLeft,  ww = wLeft;
  735. #endif
  736. #if INTERP_UV
  737.                GLfloat uu = uLeft,  vv = vLeft;
  738. #endif
  739.                GLint left = FixedToInt(fxLeftEdge);
  740.                GLint right = FixedToInt(fxRightEdge);
  741.  
  742. #if INTERP_RGB
  743.                /* need this to accomodate round-off errors */
  744.                if (ffr<0) ffr = 0;
  745.                if (ffg<0) ffg = 0;
  746.                if (ffb<0) ffb = 0;
  747. #endif
  748. #if INTERP_ALPHA
  749.                if (ffa<0) ffa = 0;
  750. #endif
  751. #if INTERP_INDEX
  752.                if (ffi<0) ffi = 0;
  753. #endif
  754.  
  755.                INNER_LOOP( left, right, iy );
  756.  
  757.                /*
  758.                 * Advance to the next scan line.  Compute the
  759.                 * new edge coordinates, and adjust the
  760.                 * pixel-center x coordinate so that it stays
  761.                 * on or inside the major edge.
  762.                 */
  763.                iy++;
  764.                lines--;
  765.  
  766.                fxLeftEdge += fdxLeftEdge;
  767.                fxRightEdge += fdxRightEdge;
  768.  
  769.  
  770.                fError += fdError;
  771.                if (fError >= 0) {
  772.                   fError -= FIXED_ONE;
  773. #ifdef PIXEL_ADDRESS
  774.                   pRow = (PIXEL_TYPE*) ((GLubyte*)pRow + dPRowOuter);
  775. #endif
  776. #if INTERP_Z
  777.                   zRow = (GLdepth*) ((GLubyte*)zRow + dZRowOuter);
  778.                   fz += fdzOuter;
  779. #endif
  780. #if INTERP_RGB
  781.                   fr += fdrOuter;   fg += fdgOuter;   fb += fdbOuter;
  782. #endif
  783. #if INTERP_ALPHA
  784.                   fa += fdaOuter;
  785. #endif
  786. #if INTERP_INDEX
  787.                   fi += fdiOuter;
  788. #endif
  789. #if INTERP_ST
  790.                   fs += fdsOuter;   ft += fdtOuter;
  791. #endif
  792. #if INTERP_STW
  793.           sLeft += dsOuter;
  794.           tLeft += dtOuter;
  795.           wLeft += dwOuter;
  796. #endif
  797. #if INTERP_UV
  798.           uLeft += duOuter;
  799.           vLeft += dvOuter;
  800. #endif
  801.                }
  802.                else {
  803. #ifdef PIXEL_ADDRESS
  804.                   pRow = (PIXEL_TYPE*) ((GLubyte*)pRow + dPRowInner);
  805. #endif
  806. #if INTERP_Z
  807.                   zRow = (GLdepth*) ((GLubyte*)zRow + dZRowInner);
  808.                   fz += fdzInner;
  809. #endif
  810. #if INTERP_RGB
  811.                   fr += fdrInner;   fg += fdgInner;   fb += fdbInner;
  812. #endif
  813. #if INTERP_ALPHA
  814.                   fa += fdaInner;
  815. #endif
  816. #if INTERP_INDEX
  817.                   fi += fdiInner;
  818. #endif
  819. #if INTERP_ST
  820.                   fs += fdsInner;   ft += fdtInner;
  821. #endif
  822. #if INTERP_STW
  823.           sLeft += dsInner;
  824.           tLeft += dtInner;
  825.           wLeft += dwInner;
  826. #endif
  827. #if INTERP_UV
  828.           uLeft += duInner;
  829.           vLeft += dvInner;
  830. #endif
  831.                }
  832.             } /*while lines>0*/
  833.  
  834.          } /* for subTriangle */
  835.  
  836.       }
  837.    }
  838. }
  839.  
  840. #undef SETUP_CODE
  841. #undef INNER_LOOP
  842.  
  843. #undef PIXEL_TYPE
  844. #undef BYTES_PER_ROW
  845. #undef PIXEL_ADDRESS
  846.  
  847. #undef INTERP_Z
  848. #undef INTERP_RGB
  849. #undef INTERP_ALPHA
  850. #undef INTERP_INDEX
  851. #undef INTERP_ST
  852. #undef INTERP_STW
  853. #undef INTERP_UV
  854.  
  855. #undef S_SCALE
  856. #undef T_SCALE
  857.